package listbyorder.access001_100.test76;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/4 10:21
 */
public class Solution2 {

    // 采用数组进行优化
    public String minWindow(String s, String t) {
        // 首先将待识别的t放入HashMap中进行构造
        int[] dp = new int[128];
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            dp[c]++;
        }
        // 定义滑动窗口的指针
        int left = 0;
        int right = 0;
        int ans_left = 0;
        int ans_right = -1;
        int ans_len = Integer.MAX_VALUE;
        int count = t.length();
        while (right < s.length()) {
            char c = s.charAt(right);
            dp[c]--;
            //代表当前符合了一个字母,如果当前遍历到字符不是t中所包含的，则一定会减成一个负数
            if (dp[c] >= 0) {
                count--;
            }
            while (count == 0) {
                // 当前窗口大小
                int temp_len = right - left + 1;
                // 如果当前窗口更小，则更新相应变量
                if (temp_len < ans_len) {
                    ans_left = left;
                    ans_right = right;
                    ans_len = temp_len;
                }
                // 得到左指针的字母
                char key = s.charAt(left);
                // 因为要把当前字母移除，所有相应次数要加 1
                dp[key]++;
                //此时的 map[key] 大于 0 了，表示缺少当前字母了，count++
                if (dp[key] > 0) {
                    count++;
                }
                left++; // 左指针右移
            }
            right++;
        }
        return s.substring(ans_left, ans_right + 1);
    }
}
